package com.example.linkedlist.circular;

/**
 * @className: CircularLinkedList
 * @description: 环形链表
 * @author: LiuZhenHe
 * @date: 2024/01/03 17:45
 **/
public class CircularLinkedList {

    private Boy first = null;

    private Boy curBoy = null;

    /**
     * 约瑟夫环:一个圈内有 n个用户，从k处开始报数，数m次，数到谁，谁出列
     * 比如一个环形有5个小孩，从第一个小孩开始数，数2两次，数到2的小孩就出列，那么顺序就是，2,4,1,5,3
     *
     * 解析：
     * 1.需要一个辅助指针，让它指向first的前一个节点，用来删除数据使用（单向链表只能用该方式删除数据）
     * 2.让first节点和辅助节点后移 k-1 次（因为从k处开始嘛，所以后移k次，k-1是因为报数包含自己，所以减一）
     * 3.通过循环，遍历环形链表，每次打印前先让first和辅助节点后移m次，然后打印该节点，打印完后，将该节点删除
     * 删除节点:先让first节点后移一位，再让辅助节点的下一个指向first节点
     * 判断是否完毕：通过判断辅助节点时候等于first节点来判断遍历是否完毕
     * （因为first会一直向后移动，移动一次就会将弹出一个数据，等first向后指仍然指向自己时或与辅助节点相等时，表示链表的数据只剩下一个了
     */
    public void joseph(int startNo, int step, int nums) {
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("数据输入不合法，请重新输入");
            return;
        }
        Boy curBoy = first;
        // 先让当前指针指向第一个节点的前一个节点
        while (curBoy.next != first) {
            curBoy = curBoy.next;
        }
        // 让当前节点和第一个节点同时向后走step-1次，因为报数包含自己本身
        for (int i = 0; i < startNo - 1; i++) {
            first = first.next;
            curBoy = curBoy.next;
        }
        while (true) {
            // 这两个条件都可判断环形链表中是否只剩下一个数据了
            //if (curBoy == first) {
            if (first.next == first) {
                System.out.println("最后一位" + first.num);
                break;
            }
            for (int j = 0; j < step - 1; j++) {
                first = first.next;
                curBoy = curBoy.next;
            }
            System.out.println("要出圈的人员编号" + first.num);
            first = first.next;
            curBoy.next = first;
        }
    }

    public Boy addNode(int number) {
        if(number<1){
            throw new RuntimeException("添加人员个数需要大于1");
        }
        for (int i = 1; i <= number; i++) {
            Boy boy = new Boy(i);
            if(first==null){
                first = boy;
                curBoy = first;
                // 让头节点自己指向自己形成环
                first.next = first;
                continue;
            }
            // 建立当前节点与要添加节点的联系
            curBoy.next =boy;
            // 让当前指针后移
            curBoy = curBoy.next;
            // 让被添加的节点的下一个节点指向第一个节点，形成环
            boy.next = first;
        }
        return first;
    }

    public void showNodes(Boy boy) {
        Boy tempNode = boy;
        while (true) {
            System.out.println(tempNode.num);
            if (tempNode.next == first) {
                break;
            }
            tempNode = tempNode.next;
        }
    }
}



class Boy{

    int num;

    Boy next;

    public Boy(int num) {
        this.num = num;
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }
}
